Pascals triangle II

Time: O(N^2); Space: O(1); easy

Given a non-negative index K where K ≤ 33, return the kth index row of the Pascal’s triangle.

Note:

  • The row index starts from 0.

Example 1:

Input: k = 3

Output: [1, 3, 3, 1]

Follow up:

Could you optimize your algorithm to use only O(K) extra space?

[1]:

class Solution1(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        result = [0] * (rowIndex + 1)

        for i in range(rowIndex + 1):
            old = result[0] = 1

            for j in range(1, i + 1):
                old, result[j] = result[j], old + result[j]

        return result

[2]:

s = Solution1()
k = 3
assert s.getRow(k) == [1, 3, 3, 1]

[3]:

class Solution2(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        row = [1]
        for _ in range(rowIndex):
            row = [x + y for x, y in zip([0] + row, row + [0])]
        return row

[4]:

s = Solution2()
k = 3
assert s.getRow(k) == [1, 3, 3, 1]

[5]:

class Solution3(object):
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        if rowIndex == 0: return [1]
        res = [1, 1]

        def add(nums):
            res = nums[:1]
            for i, j in enumerate(nums):
                if i < len(nums) - 1:
                    res += [nums[i] + nums[i + 1]]
            res += nums[:1]
            return res

        while res[1] < rowIndex:
            res = add(res)
        return res

[6]:

s = Solution3()
k = 3
assert s.getRow(k) == [1, 3, 3, 1]

[7]:

class Solution4(object):
    """
    Time: O(N^2)
    Space: O(N)
    """
    def getRow(self, rowIndex):
        """
        :type rowIndex: int
        :rtype: List[int]
        """
        result = [1]
        for i in range(1, rowIndex + 1):
            result = [1] + [result[j - 1] + result[j] for j in range(1, i)] + [1]
        return result


[8]:

s = Solution4()
k = 3
assert s.getRow(k) == [1, 3, 3, 1]